from BinaryTree import *

class Solution:
	# @param inorder, a list of integers
	# @param postorder, a list of integers
	# @return a tree node
	def buildTree(self, inorder, postorder):
		return self.__buildTree(inorder, postorder, 0, len(inorder), 0, len(postorder))

	def __buildTree(self, inorder, postorder, in_start, in_end, pos_start, pos_end):
		#print "In:"+str(in_start)+","+str(in_end)+" Po:"+str(pos_start)+","+str(pos_end)
		if in_start == in_end:
			return None
		mid_v = postorder[pos_end-1]
		mid_i = inorder.index(mid_v, in_start)
		left_size = mid_i - in_start
		right_size = in_end - mid_i - 1
		r = TreeNode(mid_v)
		r.left = self.__buildTree(inorder, postorder, 
			in_start, mid_i, 
			pos_start, pos_start+left_size)
		r.right = self.__buildTree(inorder, postorder, mid_i+1, in_end,
			pos_end-right_size-1, pos_end-1)
		return r

if __name__ == '__main__':
	ino = [2,1,4,5,3]
	pos = [2,5,4,3,1]
	so = Solution()
	r = so.buildTree(ino, pos)
	b = BinaryTree()
	b.set_tree(r)
	b.display()